/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reorderList(head *ListNode) {
	if head == nil {
		return
	}
	mid := middle(head)
	l2 := mid.Next
	mid.Next = nil
	l2 = reverse(l2)
	merge(head, l2)
}

func middle(head *ListNode) *ListNode {
	slow, fast := head, head
	for fast.Next != nil && fast.Next.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}

func reverse(head *ListNode) *ListNode {
	node := new(ListNode)
	for head != nil {
		temp := head.Next
		head.Next = node.Next
		node.Next = head
		head = temp
	}
	return node.Next
}

func merge(l1, l2 *ListNode) {
	node := new(ListNode)
	for l1 != nil && l2 != nil {
		temp := l1.Next
		node.Next = l1
		node = l1
		l1 = temp
		temp = l2.Next
		node.Next = l2
		node = l2
		l2 = temp
	}
	if l1 != nil {
		node.Next = l1
	}
}
